/**
 * @file 020.回文子字符串的个数.cc
 * @author snow-tyan (zziywang@163.com)
 * @brief {Life is too short to learn cpp.}
 * @version 0.1
 * @date 2021-11-19
 * 
 * @copyright Copyright (c) 2021
 * 
 */

#include <iostream>
#include <string>
#include <vector>
using namespace std;

class Solution
{
public:
    int countSubstrings(string s)
    {
        // 动规解 时间O(N^2) 空间O(N^2)
        // 布尔数组 dp[i][j] [i,j]左闭右闭区间是回文串
        // if s[i]==s[j]
        // 考虑区间长度小于2，大于3的情况，大于3就缩减区间
        int n = s.length();
        vector<vector<bool>> dp(n, vector<bool>(n, false));
        int cnt = 0;
        // 循环中初始化
        for (int i = n - 1; i >= 0; --i) {
            for (int j = i; j < n; ++j) {
                if (s[i] == s[j]) {
                    if (j - i <= 2) {
                        ++cnt;
                        dp[i][j] = true;
                    } else if (dp[i + 1][j - 1]) {
                        ++cnt;
                        dp[i][j] = true;
                    }
                }
            }
        }
        return cnt;
    }
};

int main()
{
    std::cout << Solution().countSubstrings("abc") << std::endl;
    std::cout << Solution().countSubstrings("aba") << std::endl;
    std::cout << Solution().countSubstrings("aaa") << std::endl;
    return 0;
}